1. Field of the Invention
The present invention relates to the design of packet forwarding mechanisms for computer networks. More specifically, the present invention relates to a method and an apparatus for performing a fast address lookup within a packet forwarder using a multi-bit trie with backtracking.
2. Related Art
As traffic on the Internet continues to increase at an exponential rate, larger volumes of packets are passing through the packet forwarding engines that forward the packets between computer systems. Hence, these packet forwarding engines are coming under increasing pressure to process packets rapidly.
Unfortunately, the address lookup process is becoming a major bottleneck to packet forwarding performance. Upon receiving a packet on an input link, a packet forwarder first performs a lookup in a forwarding table based on a destination address of the packet to determine an output link to send the packet to. As the number of destination addresses grows larger, this forwarding table can potentially become very large, which can potentially slow down the address lookup process.
A number of techniques have been developed to perform this address lookup efficiently. Most of these techniques look for a “longest matching prefix.” For example, see “Fast Address Lookups Using Controlled Prefix Expansion,” by V. Srinivasan and G. Varghese, ACM Transactions on Computer Systems, Vol. 17, No. 1, February 1999, pp. 1-40 (hereinafter referred to as the “Srinivasan paper”). Instead of storing entries for all possible destination addresses, the system described in the Srinivasan paper instead stores entries for “prefixes” that cover sets of destination addresses residing on the same network. Hence, in order to determine which output link to send a packet to, a packet forwarder simply looks for an entry in the forwarding table with the longest matching prefix, and then sends the packet to an output link specified by the entry.
The technique described in the Srinivasan paper uses a data structure known as a “multi-bit trie” to store the forwarding table entries. A multi-bit trie comprises a tree of nodes that contain arrays. For example, a 32-bit Internet Protocol (IP) address can be divided into four eight-bit portions, each one of which can be used to index a different node in the trie. Each of these nodes contains a 2n-entry array, with an entry for each of the possible 2n values of a corresponding n-bit portion of the IP address.
In the system described in the Srinivasan paper, if a specific prefix is not an exact multiple of eight bits, the prefix is expanded into multiple entries. For example, a 20-bit prefix is expanded into the 16 possible 24-bit values covered by the 20-bit prefix, and an entry for each of the 16 possible values is inserted into the trie. Hence, the 20-bit prefix 2.3.128/20 expands into 16 24-bit entries (2.3.128, 2.3.129, . . . , 2.3.143).
Although this prefix expansion technique facilitates fast address lookups, it has a number of drawbacks. (1) It complicates the process of inserting or deleting a prefix in the forwarding table because a single prefix can potentially generate a large number of entries in the forwarding table. Moreover, the prefix insertion process involves performing a complicated controlled prefix expansion operation. (2) It further complicates the prefix deletion process because the system has to first determine if an entry in the table is an “expanded prefix” or an “unexpanded prefix” in order to determine how to perform the deletion. (3) It similarly complicates the process of updating a prefix. (4) It also complicates the process of walking through the forwarding table, for example to see all the routes in the system. This is because the system must somehow distinguish between “expanded” and “unexpanded” prefixes.
Hence, what is needed is a method and an apparatus for looking up a destination address without the problems of the prefix expansion technique yet maintaining a reasonably fast lookup time.